Benvenuti nella Lezione 2. Dopo aver stabilito gli obiettivi generali di questo corso, ci immergiamo nei fondamentali Strutture Dati che costituiscono i mattoni fondamentali del design degli algoritmi: Array e Liste Collegate.
Gli Array e le Liste Collegate sono i modi più basilari e critici con cui organizziamo i dati in memoria, rappresentando il conflitto centrale tra contigui e dispersi gestione della memorizzazione.
Definizione: Una Struttura Dati è un formato specializzato per organizzare e archiviare i dati al fine di facilitarne l'accesso e la modifica efficiente.
- Gli Array immagazzinano gli elementi in contiguiposizioni di memoria, consentendo il calcolo diretto degli indirizzi degli elementi.
- Le Liste Collegate immagazzinano gli elementi in dispersiposizioni di memoria, collegate soltanto da puntatori espliciti.
- L'accesso agli Array è Indicizzazione Diretta ($O(1)$), mentre l'accesso alle Liste Collegate richiede Traversamento ($O(n)$).
- L'inserimento/eliminazione in un Array richiede lo spostamento degli elementi, con conseguente complessità di $O(n)$ complessità.
- L'inserimento/eliminazione in una Lista Collegata richiede soltanto Ricollegamento dei Puntatori, raggiungendo una complessità di $O(1)$ se la posizione $i$ è nota.
- Le Liste Collegate comportano un overhead spaziale più elevato perché ogni nodo deve contenere dati oltre al puntatore `next`.Overhead Spazialeperché ogni nodo deve contenere dati oltre al puntatore `next`.
Confronto delle Complessità
| Caratteristica | Array | Lista Collegata Singola |
|---|---|---|
| Allocazione della Memoria | Contigua (Dimensione Blocco Fissa $n$) | Dispersa (Puntatori Dinamici) |
| Tempo di Accesso | $O(1)$ | $O(n)$ |
| Inserimento/Eliminazione | $O(n)$ | $O(1)$ (se la posizione $i$ è nota) |
| Overhead Spaziale | Minimo (solamente dati) | Elevato (dati + next puntatore) |